import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * This class represents a routing table for a virtual router.
 * 
 * The IP addresses of network IDs and gateways are represented by Strings
 * which can be used to retrieve or create a true InetAddress.
 * e.g. InetAddress.getByName("255.255.255.255").
 * 
 * This class is supported by RoutingTableEntry.java.
 * 
 * @author Jonathan Jung, Timothy Hong, Ronen Adam
 * 
 */
public class RoutingTable {

    private Map<String, RoutingTableEntry> routes;

    public RoutingTable() {
        routes = new HashMap<String, RoutingTableEntry>();
    }

    /**
     * Adds an entry into the routing table.
     * 
     * @param netID
     *            - A string representing the IP address of a network ID.
     * @param subnetMask
     *            - The subnet mask associated with the network ID.
     * @param gateway
     *            - A string representing the IP address of the gateway
     *            associated with the network ID.
     */
    public void add(String netID, int subnetMask, String gateway) {
        // Strip leading '/' if found.
        if (netID.substring(0, 1).equals("/")) {
            netID = netID.substring(1);
        }

        if (gateway.substring(0, 1).equals("/")) {
            gateway = gateway.substring(1);
        }

        // Add entry.
        RoutingTableEntry entry = new RoutingTableEntry(netID, subnetMask,
                gateway);

        routes.put(netID, entry);
    }

    /**
     * Deletes an entry from the routing table.
     * 
     * @param netID - A string representing the IP address of a network ID
     *                in the table.
     */
    public void delete(String netID) {
        // Strip leading '/' if found.
        if (netID.substring(0, 1).equals("/")) {
            netID = netID.substring(1);
        }

        // Delete entry.
        routes.remove(netID);
    }

    /**
     * Returns a string representing the IP address of the gateway associated
     * with a network ID.
     * 
     * @param netID
     *            - The string representing the IP address of a network ID.
     * @return Returns a string representing the IP address of the gateway
     *         associated with the specified network ID.
     */
    private String getGateway(String netID) {
        RoutingTableEntry entry = routes.get(netID);

        return entry.getGateway();
    }

    /**
     * Returns the subnet mask value associated with a network ID.
     * 
     * @param netID
     *            - A string representing the IP address of a network ID.
     * @return Returns the subnet mask value associated with the specified
     *         network ID.
     */
    private int getSubnetMask(String netID) {
        RoutingTableEntry entry = routes.get(netID);

        return entry.getSubnetMask();
    }

    /**
     * Returns a string representing the IP address of the gateway in the table
     * associated with a network ID.
     * 
     * @param destination
     *            - A string representing the destination IP address.
     * @return A string representing the IP address of the endpoint of a route
     *         in the table. Returns <B>null</B> if no match is found.
     */
    public String getEndpoint(String destination) {
        // Strip leading '/'.
        if (destination.substring(0, 1).equals("/")) {
            destination = destination.substring(1);
        }

        // Check if the destination is directly connected.
        String result = directLookup(destination);

        // If the destination wasn't found, find the next hop.
        if (result == null) {
            result = findNetID(destination);

            // A match was found.
            if (result != null) {
                result = getGateway(result);
            }
        }

        return result;
    }

    /**
     * Find a direct match in the routing table.
     * 
     * @param destination
     *            - A string representing the destination IP address.
     * @return Returns a string representing the IP address of the associated
     *         gateway. Returns <B>null</B> if no match is found.
     */
    private String directLookup(String destination) {
        String result = null;

        if (routes.containsKey(destination)) {
            result = getGateway(destination);
        }

        return result;
    }

    /**
     * Checks each entry in the table for a match.
     * 
     * @param destination
     *            - A string representing the destination IP address.
     * @return Returns a string representing the IP address of the network ID
     *         in the table associated with the destination's gateway.
     *         Returns <B>null</B> if no match is found.
     */
    private String findNetID(String destination) {
        // Find a match in the routing table.
        boolean match = false;
        int index = 0;
        String result = null;

        Set<String> keys = routes.keySet();
        String[] temp = new String[routes.size()];
        temp = keys.toArray(temp);

        // Start searching.
        while (!match) {
            String netID = temp[index];

            // Calculate a network ID using the subnet mask.
            int subnetMask = getSubnetMask(netID);

            netID = calculateIP(destination, subnetMask);

            if (index == routes.size() - 1) {
                match = true; // No match found, but 'true' ends the loop.
            } else {
                index++; // Keep looking.
            }

            if (routes.containsKey(netID)) {
                match = true;
                result = netID; // Match found, stop looking.
            }
        }

        return result;
    }

    /**
     * Calculates an IP address using a subnet mask value.
     * 
     * @param address
     *            - A string representing the an IP address.
     * @param subnetValue
     *            - The subnet mask value.
     * @return Returns a string representing the calculated IP address.
     */
    private String calculateIP(String address, int subnetValue) {
        // 1. Calculate the subnet mask.
        int subnetMask = 0;

        if (subnetValue > 0) {
            subnetMask = 0x80000000; // '1' followed by zeros
            /*
             * Right-shifting the '1' will result in a one in each shifted
             * position. There is already a '1' in the mask so the subnet value
             * is '1' too many bits for an accurate shift. Subtract '1' to fix.
             */
            subnetMask = subnetMask >> (subnetValue - 1);
        }

        // 2. Calculate the IP using the subnet mask.

        // Isolate each octet from the IP string.
        String[] addressSlices = address.split("\\.");

        // Assemble an integer ip value from the octets.
        // Shift each octet to its appropriate position in a 32-bit value.
        int octet1 = Integer.valueOf(addressSlices[0]) << 24;
        int octet2 = Integer.valueOf(addressSlices[1]) << 16;
        int octet3 = Integer.valueOf(addressSlices[2]) << 8;
        int octet4 = Integer.valueOf(addressSlices[3]);

        int ipValue = octet1 + octet2 + octet3 + octet4;

        // 3. Perform the bitwise-and operation with the IP and the subnet mask.
        int newIpValue = ipValue & subnetMask;

        // 4. Extract the calculated octets.
        int octet1Mask = 0x00FFFFFF;
        int octet2Mask = 0xFF00FFFF;
        int octet3Mask = 0xFFFF00FF;
        int octet4Mask = 0xFFFFFF00;

        // Shift the octets back to individual 8-bit values.
        octet1 = ((newIpValue | octet1Mask) ^ octet1Mask) >> 24;
        /*
         * The first octet may have been corrupted by overflow if the original
         * value was greater than 127. The result of a value of '128' - '255'
         * can be corrected by adding '256' to return a positive 8-bit value.
         */
        if (octet1 < 0) {
            octet1 += 256;
        }

        octet2 = ((newIpValue | octet2Mask) ^ octet2Mask) >> 16;
        octet3 = ((newIpValue | octet3Mask) ^ octet3Mask) >> 8;
        octet4 = (newIpValue | octet4Mask) ^ octet4Mask;

        // 5. Assemble the calculated IP.
        StringBuilder sb = new StringBuilder();
        sb.append(octet1);
        sb.append(".");
        sb.append(octet2);
        sb.append(".");
        sb.append(octet3);
        sb.append(".");
        sb.append(octet4);
        sb.trimToSize();

        return sb.substring(0);
    }

    /*
     * Prints the contents of the routing table.
     */
    public void print() {
        
        System.out.println(toString());
    }
    
    /**
     * Returns a string representation of the contents of the routing table.
     * 
     * @return Returns a string representation of the contents of the routing
     *         table.
     */
    public String toString() {

        StringBuilder result = new StringBuilder();

        result.append("====================================================");
        result.append("\n");
        result.append(String.format("%-16s    %-3s    %-16s", "Network ID",
                "Subnet Mask", "Gateway"));
        result.append("\n");
        result.append("----------------------------------------------------");
        result.append("\n");

        Set<String> keys = routes.keySet();

        for (String netID : keys) {
            RoutingTableEntry entry = routes.get(netID);
            result.append(entry);
            result.append("\n");
        }

        result.append("====================================================");
        result.append("\n");

        result.trimToSize();

        return result.substring(0);
    }
}
